/*
 * Copyright (c) 2009-2010 HIT Microelectronic Center
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *
 * Authors: Gou Pengfei
 *
 * Date: Dec. 2009
 *       Nov. 2010
 *
 */

#ifndef __CPU_EDGE_BLOCK_HH__
#define __CPU_EDGE_BLOCK_HH__

#include <bitset>

#include "base/statistics.hh"
#include "base/bitfield.hh"
#include "cpu/edge/base_block.hh"

/**
 * This class will hold all the dynamic staff of instruction block
 * such as the instructions belongs to a block and some execution flags
 * of the block. This class is TRIPS-specific...
 * */
template <class Impl>
class SimpleEdgeBlock : public BaseEdgeBlock<Impl>
{
  public:
    typedef typename Impl::CPU CPU;
    typedef typename Impl::DynInstPtr DynInstPtr;

    typedef TheISA::BlockID BlockID;
    typedef TheISA::HeaderInfo HeaderInfo;
    typedef TheISA::InstID InstID;
    typedef TheISA::ExitID ExitID;
    typedef TheISA::ConsumerType ConsumerType;
    typedef TheISA::ExitType ExitType;
    typedef TheISA::ConsumerBitfield ConsumerBitfield;
    typedef std::bitset<TheISA::HeaderSize> HeadMask;
    typedef std::bitset<TheISA::StoreMaskNum> StoreMask;
    typedef std::bitset<TheISA::MaxExitsInBlock> ExitMask;
    typedef TheISA::StaticMapBitfield StaticMapBitfield;

    /** A class for each ld/st entry. */
    class LdstEntry 
    {
      public:
        LdstEntry()
        :valid(false),
        nullified(false),
        executed(false),
        store(false),
        executedInstIdx(-1),
        preExeEffAddr(0),
        preExeAccSize(0),
        preExeInstIdx(-1),
        preExeNullified(false),
        preExeFault(false)
        {
        }

        ~LdstEntry()
        {
        }

        /** Is this entry valid? */ 
        bool valid;
        /** Is this entry nullified? */
        bool nullified;
        /** Has this entry been executed? */
        bool executed;
        /** Is this a store entry? */
        bool store;
        
        /**
         * Instruction index of all instructions belong to this entry will be
         * pushed here.
         * */
        std::vector<int> instContainerIdxs;

        /**
         * Instruction index of the finally executed instruction will be marked
         * here.
         * */
        int executedInstIdx;

        /**
         * Effective address of this entry generated by the
         * pre-execute model
         * */
        Addr preExeEffAddr;

        /**
         * Access size of this entry generated by the pre-execute
         * model
         * */
        int preExeAccSize;

        /**
         * Pre-execute model generated instruction index of the
         * finally executed instruction.
         * */
        int preExeInstIdx;

        /** Has pre-execute model generated nullified flag? */
        bool preExeNullified;

        /** Has pre-execute model generated a fault for this entry? */
        bool preExeFault;

        void reset()
        {
            valid = nullified = executed = store = false;
            executedInstIdx = -1;
            instContainerIdxs.clear();
            preExeInstIdx = -1;
            preExeAccSize = 0;
            preExeEffAddr = 0;
            preExeNullified = false;
            preExeFault = false;
        }
    };

    SimpleEdgeBlock(BlockID blockID, CPU* cpu);

    ~SimpleEdgeBlock();

#ifndef NDEBUG

    struct registerIdxComp
    {
        bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
        {
            return (lhs->getMappedDestReg(0) < rhs->getMappedDestReg(0));
        }
    };

    struct effAddrComp
    {
        bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
        {
            return (lhs->effAddr < rhs->effAddr);
        }
    };

#endif

  protected:

    /** 
     * These flags are given by the compiler. See trips processor
     * manual for further information. 
     * */
    uint32_t mark;
    uint32_t type;
    uint32_t sMask;
    uint32_t xFlags;
    int chunkNum;

    /** These flags are determined dynamically. */ 
    HeadMask readMask;
    HeadMask writeMask;

    /** Frame id of this block during execution. */
    int frameID;

    /** 
     * This is the exit mask indicating which exit id is available in
     * this block.
     * */
    ExitMask exitMask;

    /** 
     * This is the dynamic record indicating which store has been
     * executed. 
     * */
    StoreMask sMaskFlag;

    /** Start address of next block in program order*/
    Addr nextBlockPC;

    /** Branch target of this block. */
    Addr branchTarget;

    /** Predicted branch target of this block. */
    Addr predBranchTarget;

    /** Exit id of this block. */ 
    ExitID exitID;

    /** Predicted exit id of this block. */
    ExitID predExitID;

    /** Exit type of this block. */
    ExitType exitType;

    /** Predicted exit type of this block. */
    ExitType predExitType;

    uint32_t numReceivedStore;
    uint32_t numReceivedWrite;
    uint32_t numReceivedExit;

    /** 
     * This data structure will hold all the instructions belong to
     * this block. A vector is used because the number of instructions
     * and the behavior of these instructions are deterministic.
     * Further more, I didn't name it as 'Instruction Queue' due to
     * some concerns of disambiguation (There is a 'Instruction Queue'
     * in Execution stage.).
     * */
    std::vector<DynInstPtr> instContainer;

    /** 
     * This data structure will hold all the ld/st instructions.
     * Actually, there is no real instruction in each entry, instead,
     * a list of instContainer ids, which holds the positions of ld/st
     * instructions in instContainer, is introduced to help finding
     * ld/st instructions in instContainer.
     * */
    std::vector<LdstEntry> ldstContainer;

    /**
     * This data structure will hold all the register reads.
     * */
    std::vector<DynInstPtr> readContainer;

    /**
     * This data structure will hold all the register writes.
     * */
    std::vector<DynInstPtr> writeContainer;

    // The following data structures are used for the GOD mode.
   
    /**
      *  List of ready instructions.
      */
    std::vector<int> readyList;

    /** 
      * List of compteted instructions belonged
      * to current pass.
      */
    std::vector<int> completedList;

    /** 
      *  List of instructions need to be replayed.
      */
    std::vector<int> replayList;

    /**
     * Wake up instructions according to dataflow relation ship. This
     * function works just the same as in InstructionQueue class. This
     * function is specifically used by the execute() method in this
     * block. You can not invoke this method outside of this class.
     * */
    int wakeDependents(DynInstPtr& completed_inst);

    /**
     * This is a bitset vector to record which instruction will get a
     * matched predication during the execution. It is used to
     * implement the perfect predication execution policy.
     *
     * False means the instruction in this position doesn't have valid
     * predication status or will get an unmatched predication in execution.
     *
     * True means the instruction in this position has a valid
     * predication status and will get a matched predication in
     * execution.
     * */
    std::bitset<TheISA::MaxInstsInBlock> predicationStatus;

    /** A container to record results of all TEST instructions for predication
     * path tracking. Each TEST inst corresponds to one bit in this container
     * in their inst ID order, i.e., testInstPath[0] is the first TEST inst in
     * one block. If one bit is set, means the corresponding TEST delivers a
     * TRUE value, vice versa.*/
    std::vector<bool> testInstPath;

  public:

    /* These member variables describe the characteristic of this
     * dynamic block. */

    /** Real branch target. */
    Addr getBranchTarget()          const { return branchTarget; }

    /** Predicted branch target. */
    Addr getPredBranchTarget()      const { return predBranchTarget; }

    /** Next start pc of this block in program order. */
    Addr getNextBlockPC()           const { return nextBlockPC; }

    /** How many chunks does this block contain? */
    int getChunkNum()               const { return chunkNum; }

    /** How many register writes have this block received? */
    uint32_t getNumReceivedWrite()  const { return numReceivedWrite; }

    /** How many stores have this block received? */
    uint32_t getNumReceivedStore()  const { return numReceivedStore; }

    /** How many exits have this block received? */
    uint32_t getNumReceivedExit()   const { return numReceivedExit; }

    /** Get the static store mask of this block. */
    uint32_t getStoreMask()         const { return sMask; }

    /** Get the dynamic exit id of this block. */
    TheISA::ExitID getExitID()      const { return exitID; }

    /** Get the dyanmic predicted exit id of this block. */
    TheISA::ExitID getPredExitID()    const { return predExitID; }

    /** Get the dynamic exit type of this block. */
    TheISA::ExitType getExitType()  const { return exitType; }

    /** Get the predicted exit type of this block. */
    TheISA::ExitType getPredExitType() const {return predExitType; }

    /** Get the number of exits of this block. */
    int getExitNum()                const { return exitMask.count(); }

    /** Get the read mask of this block. */
    HeadMask& getReadMask() { return readMask; }

    /** Get the write mask of this block. */
    HeadMask& getWriteMask() { return writeMask; }

    /** Get the size of this block without considering heads. */
    int getBlockSize() const { return chunkNum * TheISA::ChunkSizeInWords; }

    /** Get the dynamic frame ID of this block. */
    int getFrameID() const 
    {
        assert(frameID >= 0 && frameID < Impl::MaxFrameNum);
        return frameID;
    }

    /** Set the predication status of an instruction. */
    void setPredicationStatus(int position)
    {
        assert(position < getBlockSize());
        assert(instContainer[position]);
        assert(instContainer[position]->staticInst->getPredication()
               == TheISA::PredUponTrue ||
               instContainer[position]->staticInst->getPredication()
               == TheISA::PredUponFalse);

        predicationStatus.set(position);
    }

    /** Get the predication status of an instruction. */
    bool getPredicationStatus(int position) const
    { 
        assert(position < getBlockSize());
        assert(instContainer[position]);
        assert(instContainer[position]->staticInst->getPredication()
               == TheISA::PredUponTrue ||
               instContainer[position]->staticInst->getPredication()
               == TheISA::PredUponFalse);

        return predicationStatus[position];
    }

    /** Set the predication status on a whole. */
    void setPredicationStatus(std::bitset<TheISA::MaxInstsInBlock> &pred_status) 
    {
        predicationStatus = pred_status;
    }

    /** Get the whole data structure holding the predication status.*/
    std::bitset<TheISA::MaxInstsInBlock> getPredicationStatus() const
    {
        return predicationStatus;
    }

    /** Get the predication pattern for next-block predictors. */
    uint64_t getPredicationPattern() const
    {
        // TODO : assume predicationStatus has size of 128.
        uint32_t h127_h96 = (std::bitset<32>(predicationStatus.to_string())).to_ulong();
        uint32_t h95_h64 = (std::bitset<32>((predicationStatus << 32).to_string())).to_ulong();
        uint32_t h63_h32 = (std::bitset<32>((predicationStatus << 64).to_string())).to_ulong();
        uint32_t h31_h0 = (std::bitset<32>((predicationStatus << 96).to_string())).to_ulong();
        
//        uint64_t hi = (((uint64_t)h127_h96) << 32) | ((uint64_t)h95_h64);
//        uint64_t lo = (((uint64_t)h63_h32) << 32) | ((uint64_t)h31_h0);

        return (h127_h96 ^ (h127_h96 >> 16)) ^
            (h95_h64 ^ (h95_h64 >> 16)) ^
            (h63_h32 ^ (h63_h32 >> 16)) ^
            (h31_h0 ^ (h31_h0 >> 16));
    }

    /** Set the test inst path, which should be set by a pre-executed cpu. */
    void setTestInstPath(std::vector<bool> & in_path)
    {
        testInstPath = in_path;
    }

    /** Get the test inst path, which should be set by a pre-executed cpu.*/
    uint64_t getTestInstPath()
    {
        uint64_t temp_path = 0;

        for (int idx = 0; idx < testInstPath.size() && idx < 64; idx++) {
            if (testInstPath[idx]) {
                temp_path = insertBits(temp_path, idx, 1);
            }
        }
        return temp_path;
    }

    void setBranchTarget(Addr branch_pc);

    void setPredBranchTarget(Addr pred_branch_pc);

    /** We set next block pc when we depack the header,
     *  but I still add this method to modify next block pc
     *  manually.
    */
    void setNextBlockPC(Addr next_block_pc);

    /** If this block is mispredicted? */
    bool misPredicted();

    /** If the exit of this block is mispredicted? */
    bool exitMispredicted();

    /** If the branch type of this block is mispredicted? */
    bool exitTypeMispredicted();

    /** If the branch type of this block is mispredicted for
     * sequential branch. */
    bool seqMispredicted();

    /** Put the instruction to a specific position. */
    void addInst(DynInstPtr &inst, int position);

    /** Get the instruction of a specific position. */
    DynInstPtr getInst(int position);

    /** Put the head inst (read/write) to a specific position. */
    void addHead(DynInstPtr &inst, int position);

    /** Get read of a specific position. */
    DynInstPtr getRead(int position);

    /** Get write of a specific position. */
    DynInstPtr getWrite(int position);

    /** Get the idx of memory references to a specific LSID. */
    std::vector<int>& getMemoryReferenceIdx(TheISA::LsID lsid);

    /** Inquire if a ldst entry is valid. */
    bool isLdstEntryValid(TheISA::LsID lsid)
    {
        return ldstContainer[lsid].valid;
    }

    /** Remove all the instructions of this block. */
    void removeAllInsts();


    /** Assemble header info from fetched header insts.
     *  Return true if everything is OK.
     *  Return false if the header is not compitable with TRIPS ISA
     *  which means an address with unaligned inst block boundary
     *  has been used.
    */
    bool depackHeader(HeaderInfo& info);

    /** 
     * This will explain what consumer id means
     * and where will each inst locates.
    */
    void map();

    void setFrameID(int frame_id) 
    {
        assert(frame_id < Impl::MaxInFlightBlockNum && frame_id >= 0);
        frameID = frame_id;
    }

    bool isCompletionCondSatisfied();

    void incReceivedWrite() { numReceivedWrite++; }

    void incReceivedStore(TheISA::LsID lsid, TheISA::InstID inst_id)
    { 
        assert(sMaskFlag[lsid] == 0);

        numReceivedStore++; 
        
        sMaskFlag.set(lsid); 

        ldstContainer[lsid].executed = true;

        ldstContainer[lsid].executedInstIdx = inst_id;
    }

    void nullifyStore(TheISA::LsID lsid)
    {
        assert(ldstContainer[lsid].valid &&
               ldstContainer[lsid].store);

        ldstContainer[lsid].nullified = true;
    }

    /**
     * Get the first store that has a smaller lsid than the parameter. 
     * */
    TheISA::LsID getLastStore(TheISA::LsID lsid);

    /** 
     * Get the first store that has a smaller lsid and a voilated
     * address.
     * */
    TheISA::LsID getLastStore(DynInstPtr &inst);

    /** 
      * Get the first unexecuted store slot in LSID order.
      * Stores with such a LSID will behave like a memory blocker.
      */
    TheISA::LsID getMemBlockerLSID();

    void incReceivedExit()
    {
        assert(numReceivedExit == 0); 
        numReceivedExit++;
    }

    void recordExitID(ExitID exit_id)
    { 
        assert(numReceivedExit == 1); 
        exitID = exit_id;
    }

    /** @TODO Dirty method ... */
    void recordExitType(bool isCall, bool isReturn, bool isIndirect);

    void setPredInfo(ExitID exit_id, ExitType exit_type, Addr pc)
    {
        predExitID = exit_id;
        predExitType = exit_type;
        predBranchTarget = pc;
    }

    void setPredExitType(ExitType exit_type)
    {
        predExitType = exit_type;
    }

    void setPredExitID(ExitID exit_id)
    {
        predExitID = exit_id;
    }

    /** Number of executed insts of this block. */ 
    int executedInsts;

    /** 
     * Number of executed move instructions of this block. 
     * These instructions are expected to be ignored in caculating the
     * IPC.
     * */
    int executedMovs;

    /** Dump the output of this block including stores and writes. */
    void dumpOutput();

    /** 
     * Set the branch target to be the value in return address
     * register for a block that contains a system call. Return address
     * is in TheISA::ReturnAddressReg which will be generated by a
     * write instruction in the same block.
     * */
    void setSyscallBranchTarget();

    /**
     * Set the effective address, access size and the instruction id
     * of a specific ldstEntry.
     * */
    void setLdstEntry(TheISA::LsID lsid, Addr eff_addr,
            int acc_size, TheISA::InstID inst_id, bool nullified, bool fault)
    {
        assert(ldstContainer[lsid].valid);
        assert(instContainer[inst_id]);

        // Set the ldstEntry
        ldstContainer[lsid].preExeEffAddr = eff_addr;
        ldstContainer[lsid].preExeAccSize = acc_size;
        ldstContainer[lsid].preExeInstIdx = inst_id;
        ldstContainer[lsid].preExeNullified = nullified;
        ldstContainer[lsid].preExeFault = fault;

        // Set the instruction
        instContainer[inst_id]->preExeEffAddr = eff_addr;
        instContainer[inst_id]->preExeAccSize = acc_size;
        instContainer[inst_id]->preExeNullified = nullified;
        instContainer[inst_id]->preExeFault = fault;
        instContainer[inst_id]->preExeValid = true;
    }
};

#endif //__CPU_EDGE_BLOCK_HH__
